package fun.coding.leetcode;

public class MaximumProductSubarray {

	public static void main(String[] args) {
		// [-4,-3,-2] -> 12
		// [2,-1,1,1] -> 2
		// They will all remove the leading 0s
		System.out.println(Integer.valueOf("03"));
		System.out.println(Integer.parseInt("03"));
		
		MaximumProductSubarray mps = new MaximumProductSubarray();
		int[] a = {-4, -3, -2};
		int[] b = {2, -1 , 1, 1};
		
		System.out.println(mps.maxProduct(a));
		System.out.println(mps.maxProduct(b));
		
	}
	
    public int maxProduct(int[] A) {
        if (A.length == 1) return A[0];
        
        int l = A.length;
        
        int[] pos = new int[l];
        int[] neg = new int[l];
        
        pos[0] = A[0];
        neg[0] = A[0];
        int max = A[0];
        
        for (int i = 1; i < l; ++i) {
        	pos[i] = Math.max(A[i], Math.max(A[i] * pos[i-1], A[i] * neg[i-1]));
        	neg[i] = Math.min(A[i], Math.min(A[i] * pos[i-1], A[i] * neg[i-1]));
        	
        	if (pos[i] > max) {
        		max = pos[i];
        	}
        }
        return max;
    }
    
    /* leetcode solution. 
    public int maxProduct(int[] A) {
    	   assert A.length > 0;
    	   int max = A[0], min = A[0], maxAns = A[0];
    	   for (int i = 1; i < A.length; i++) {
    	      int mx = max, mn = min;
    	      max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
    	      min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
    	      maxAns = Math.max(max, maxAns);
    	   }
    	   return maxAns;
    	}
	*/
}
